<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  
  
  <link rel="shortcut icon" href="../../img/favicon.ico">
  <title>0153 find minimum in rotated sorted array - 力扣问题题解（简易版）</title>
  <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Lato:400,700|Roboto+Slab:400,700|Inconsolata:400,700" />

  <link rel="stylesheet" href="../../css/theme.css" />
  <link rel="stylesheet" href="../../css/theme_extra.css" />
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/styles/github.min.css" />
  
  <script>
    // Current page data
    var mkdocs_page_name = "0153 find minimum in rotated sorted array";
    var mkdocs_page_input_path = "\u7b2c 3 \u7ae0 \u4e8c\u5206\u67e5\u627e/0153-find-minimum-in-rotated-sorted-array.md";
    var mkdocs_page_url = null;
  </script>
  
  <script src="../../js/jquery-2.1.1.min.js" defer></script>
  <script src="../../js/modernizr-2.8.3.min.js" defer></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/highlight.min.js"></script>
  <script>hljs.initHighlightingOnLoad();</script> 
  
</head>

<body class="wy-body-for-nav" role="document">

  <div class="wy-grid-for-nav">

    
    <nav data-toggle="wy-nav-shift" class="wy-nav-side stickynav">
    <div class="wy-side-scroll">
      <div class="wy-side-nav-search">
        <a href="../.." class="icon icon-home"> 力扣问题题解（简易版）</a>
        <div role="search">
  <form id ="rtd-search-form" class="wy-form" action="../../search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" title="Type search term here" />
  </form>
</div>
      </div>

      <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../..">Welcome to MkDocs</a>
                    </li>
                </ul>
                <p class="caption"><span class="caption-text">广度优先遍历</span></p>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../../%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86/0126-word-ladder-ii/">0126 word ladder ii</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86/0127-word-ladder/">0127 word ladder</a>
                    </li>
                </ul>
                <p class="caption"><span class="caption-text">第 2 章 排序算法</span></p>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../../%E7%AC%AC%202%20%E7%AB%A0%20%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/0001-two-sum/">0001 two sum</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../%E7%AC%AC%202%20%E7%AB%A0%20%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/0011-container-with-most-water/">0011 container with most water</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../%E7%AC%AC%202%20%E7%AB%A0%20%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/">归并排序</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../%E7%AC%AC%202%20%E7%AB%A0%20%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F/">插入排序</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../%E7%AC%AC%202%20%E7%AB%A0%20%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F/">选择排序</a>
                    </li>
                </ul>
                <p class="caption"><span class="caption-text">第 3 章 二分查找</span></p>
                <ul class="current">
                    <li class="toctree-l1"><a class="reference internal" href="../0035-search-insert-position/">0035 search insert position</a>
                    </li>
                    <li class="toctree-l1 current"><a class="reference internal current" href="./">0153 find minimum in rotated sorted array</a>
    <ul class="current">
    </ul>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../0154-find-minimum-in-rotated-sorted-array-ii/">0154 find minimum in rotated sorted array ii</a>
                    </li>
                </ul>
      </div>
    </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">

      
      <nav class="wy-nav-top" role="navigation" aria-label="top navigation">
        <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
        <a href="../..">力扣问题题解（简易版）</a>
      </nav>

      
      <div class="wy-nav-content">
        <div class="rst-content">
          <div role="navigation" aria-label="breadcrumbs navigation">
  <ul class="wy-breadcrumbs">
    <li><a href="../..">Docs</a> &raquo;</li>
    
      
        
          <li>第 3 章 二分查找 &raquo;</li>
        
      
    
    <li>0153 find minimum in rotated sorted array</li>
    <li class="wy-breadcrumbs-aside">
      
    </li>
  </ul>
  
  <hr/>
</div>
          <div role="main">
            <div class="section">
              
                <ul>
<li>假设数组中不存在重复元素。</li>
</ul>
<p>暴力解法：</p>
<p>Java 代码：</p>
<pre><code class="java">public class Solution {

    public int findMin(int[] nums) {
        int len = nums.length;
        int minVal = nums[0];
        for (int i = 1; i &lt; len; i++) {
            minVal = Math.min(minVal, nums[i]);
        }
        return minVal;
    }
}
</code></pre>

<h2 id="_1">方法一：二分查找</h2>
<p>典型的例子：<code>nums[left] &lt; nums[mid]</code> 的时候，最小值可能在后半部分，也可能在前半部分。</p>
<ul>
<li><code>[4, 5, 6, 1, 2]</code>；</li>
<li><code>[1, 2, 3, 4, 5]</code>；</li>
</ul>
<p>故：<strong>只能使用中间数和右边界比较</strong>。</p>
<p>Java 代码：</p>
<pre><code class="java">public class Solution {

    public int findMin(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return -1;
        }

        int left = 0;
        int right = len - 1;
        while (left &lt; right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] &gt; nums[right]) {
                // 下一轮搜索区间在 [mid + 1, right]
                left = mid + 1;
            } else {
                // 下一轮搜索区间在 [left, mid]
                right = mid;
            }
        }
        // 非空数组一定存在最小值
        return nums[left];
    }
}
</code></pre>

<p>Java 代码：</p>
<pre><code class="java">public class Solution {

    public int findMin(int[] nums) {
        int len = nums.length;

        int left = 0;
        int right = len - 1;
        while (left &lt; right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] &lt; nums[right]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
}
</code></pre>

<h2 id="_2">方法二：分治算法</h2>
<blockquote>
<p>比较下面两种写法。</p>
</blockquote>
<p>Java 代码：</p>
<pre><code class="java">public class Solution {

    // 分治算法

    public int findMin(int[] nums) {
        int len = nums.length;
        return findMin(nums, 0, len - 1);
    }

    private int findMin(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }

        if (left + 1 == right) {
            return Math.min(nums[left], nums[right]);
        }
        int mid = left + (right - left) / 2;

        if (nums[mid] &lt; nums[right]) {
            // 右边是顺序数组，[mid + 1 , right] 这个区间里的元素可以不看
            return findMin(nums, left, mid);
        } else {
            // nums[mid] &gt; nums[right]
            // 左边是顺序数组，[left + 1, mid] 这个区间里的元素可以不看
            return findMin(nums, mid + 1, right);
        }
    }
}
</code></pre>

<blockquote>
<p>说明：下面的代码：</p>
<p><code>java
if (nums[left] &lt; nums[right]) {
    return nums[left];
}</code></p>
<p>是精髓。</p>
</blockquote>
<p>Java 代码：</p>
<pre><code class="java">public class Solution {

    public int findMin(int[] nums) {
        int len = nums.length;
        return findMin(nums, 0, len - 1);
    }

    public int findMin(int[] nums, int left, int right) {
        if (left + 1 &gt;= right) {
            return Math.min(nums[left], nums[right]);
        }
        if (nums[left] &lt; nums[right]) {
            return nums[left];
        }

        int mid = left + (right - left) / 2;
        return Math.min(findMin(nums, left, mid), findMin(nums, mid + 1, right));
    }
}
</code></pre>
              
            </div>
          </div>
          <footer>
  
    <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
      
        <a href="../0154-find-minimum-in-rotated-sorted-array-ii/" class="btn btn-neutral float-right" title="0154 find minimum in rotated sorted array ii">Next <span class="icon icon-circle-arrow-right"></span></a>
      
      
        <a href="../0035-search-insert-position/" class="btn btn-neutral" title="0035 search insert position"><span class="icon icon-circle-arrow-left"></span> Previous</a>
      
    </div>
  

  <hr/>

  <div role="contentinfo">
    <!-- Copyright etc -->
    
  </div>

  Built with <a href="https://www.mkdocs.org/">MkDocs</a> using a <a href="https://github.com/snide/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>.
</footer>
      
        </div>
      </div>

    </section>

  </div>

  <div class="rst-versions" role="note" aria-label="versions">
    <span class="rst-current-version" data-toggle="rst-current-version">
      
      
        <span><a href="../0035-search-insert-position/" style="color: #fcfcfc;">&laquo; Previous</a></span>
      
      
        <span style="margin-left: 15px"><a href="../0154-find-minimum-in-rotated-sorted-array-ii/" style="color: #fcfcfc">Next &raquo;</a></span>
      
    </span>
</div>
    <script>var base_url = '../..';</script>
    <script src="../../js/theme.js" defer></script>
      <script src="../../js/extra.js" defer></script>
      <script src="../../js/baidu-tongji.js" defer></script>
      <script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-MML-AM_CHTML" defer></script>
      <script src="../../search/main.js" defer></script>
    <script defer>
        window.onload = function () {
            SphinxRtdTheme.Navigation.enable(true);
        };
    </script>

</body>
</html>
